#include "arbol_b.h"

ArbolB::ArbolB(std::string nombre, unsigned int tam_bloque):Archivo(nombre , tam_bloque){
	std::string nombre_libres = nombre + _EXT_BBLL_;
	bloques_libres = new ArchBloquesLibres(nombre_libres,tam_bloque);
	bloques_libres->agregar_observador(Buffer::get_instance());
	this->base = NULL;
	base_hoja = new TipoInt(0);
	base_interno = new TipoInt(0);
}
	
ArbolB::~ArbolB(){
	
	this->cerrar();
	delete(bloques_libres);	
	if(base != NULL){
		delete base;
		base = NULL;
	}
	delete base_hoja;
	delete base_interno;
}
		
void ArbolB::crear() throw(ExcepCreandoArch){
	std::string dest = "./DATA/" + this->get_nombre();
	
	this->fd = ManejadorArchivos::get_instance()->crear_archivo(dest);
	if ( this->fd == -1 )
		throw ExcepCreandoArch (ManejadorErrores::get_msg_error(errno) + " Archivo: " + this->get_nombre());
	
	try{
		bloques_libres->crear();
		crear_bloque(); //para el header
		crear_bloque(0); //para la raiz
		escribir_cant_bloques(this->get_cant_bloques());
	}
	catch(ExcepEscribirBloque &e){
		throw ExcepCreandoArch ("Error - No se pudo crear el archivo " + this->get_nombre() );
	}
	
}
	
void ArbolB::abrir() throw(ExcepAbriendoArch){
	
	if (this->fd != -1)
		throw ExcepAbriendoArch("Error - El archivo: " + this->get_nombre() + " ya estaba abierto.");
	else{
		std::string dest = "./DATA/" + this->get_nombre();
		this->fd = ManejadorArchivos::get_instance()->abrir_archivo(dest);
		if ( this->fd == -1)
			throw ExcepAbriendoArch (ManejadorErrores::get_msg_error(errno) + " Archivo: " + this->get_nombre());
		
		bloques_libres->abrir(); //arroja una excepcion en caso de no poder abrirlo
		bloques_libres->agregar_observador(Buffer::get_instance());
		this->cant_bloques = leer_cant_bloques();
	}		
	
}
		
void ArbolB::eliminar(){

	//Elimino el archivo de espacios libres
	bloques_libres->eliminar();
	this->cerrar();
	std::string mi_ruta = "./DATA/"+get_nombre();
	remove(mi_ruta.c_str());	
	
}

void ArbolB::cerrar(){
	
	if(fd != -1){
		bloques_libres->cerrar();
		escribir_cant_bloques(this->cant_bloques);
		this->set_cambio();
		this->avisar_observadores(NULL);
		ManejadorArchivos::get_instance()->cerrar_archivo(this->fd);
		
		this->fd = -1;
	}	
}
		
void ArbolB::ingresar(TipoDato * clave, TipoInt * dato) throw(ExcepArchCerrado, ExcepBloqueTam, ExcepErrorTipos,  ExcepRegExistente, ExcepLeerBloque){
	
	if( fd != -1){
		assert(base != NULL);//ESTO ROMPE SI NO HICIERON LAS COSAS BIEN
		
		if( clave->get_codigo_tipo() != base->get_codigo_tipo() )
			throw ExcepErrorTipos("Error - La clave es de tipo incorrecto");
		
		Debug::get_instance()->mostrar_mensaje("<ARBOL> Se ingresa en el arbol " + this->get_nombre() + "." );
		//TipoInt * dato_consultado = consultar(clave);
		//if (dato_consultado == NULL ){
			unsigned int tam = clave->get_tamanio_serializado();
			tam += dato->get_tamanio_serializado();
			//Verifico que el registro tenga menor tamanio que el bloque
			if( tam <= this->get_tam_bloque() - 4){ 
				//obtengo la raiz
				Bloque * raiz = Buffer::get_instance()->get_bloque(*this,_NODO_RAIZ_);
				//creo un nodo nuevo, le paso estos valores porque ya estan
				//verificados los tipos
				Nodo * nodo_raiz = new Nodo(raiz,clave, dato);
				ElemNodo * elem = new ElemNodo;
				elem->der = Nodo::BAD_REF;
				elem->izq = Nodo::BAD_REF;
				elem->clave = clave;
				elem->dato = dato;
				//si devuelve false, quiere decir que el overflow de la
				//raiz no se soluciono, entonces lo manejo.
				//Tener en cuenta que en nodo_raiz llega la raiz y en elem
				//me llega el que desborda
				if(!ingresar_interno(elem ,nodo_raiz))
					overflow_en_raiz(nodo_raiz, elem);
				delete nodo_raiz;
				delete raiz;
				delete elem->dato;
				delete elem->clave;
				delete elem;
			}
			else{
				throw ExcepBloqueTam("Error - El dato a ingresar es mas grande que el tamano del bloque de " + this->get_nombre() + ". ");
			}
		/*}
		else{
			delete dato_consultado;
			throw ExcepRegExistente("Error - El registro que intenta ingresar ya existe en el archivo. ");
		}*/
	}
	else
		throw ExcepArchCerrado("Error - El archivo : "+ this-> get_nombre() +" esta cerrado. ");

}
void ArbolB::overflow_en_raiz(Nodo * raiz, ElemNodo * elem){
	
	
	Debug::get_instance()->mostrar_mensaje("<ARBOL> Se produjo un overflow en la raiz del arbol " + this->get_nombre() + ".");
	
	//pido dos bloques libres, porque la raiz siempre va a necesitar 2.
	//creo los nodos derechos e izquierdos
	Bloque * derecho = get_bloque_libre(raiz->get_nivel() );
	Nodo nodo_derecho(derecho, elem->clave, elem->dato);
	Bloque * izquierdo = get_bloque_libre(raiz->get_nivel() );
	Nodo nodo_izquierdo(izquierdo, elem->clave, elem->dato);
	
	//intercambio con el derecho. 
	//El derecho queda con el nivel que tenia el padre
	char * temp = raiz->get_bloque()->get_contenido();
	izquierdo->set_contenido(temp, derecho->get_size() );
	delete[] temp;
	raiz->vaciar();
	
	//divido entre el derecho y el izquierdo. Ambos quedan con el mismo
	//nivel, que es el que era de la raiz	
	char result = nodo_izquierdo.dividir_nodo(&nodo_derecho, &elem->clave, (TipoDato**)(&elem->dato));
	//le setteo un nivel mas que los hijos pero si antes era el cero.
	//en otro caso me lo settean ya desde antes
	
	//if( raiz->get_nivel() == 0 )
		raiz->set_nivel( nodo_derecho.get_nivel() + 1);
	
	//inserto el elemento en la raiz
	raiz->ingresar_elemento(elem->clave, elem->dato);
	//asigno el derecho
	raiz->set_ref_der(derecho->get_num_bloque() );
	//asigno el izquierdo
	raiz->set_ref_izq(izquierdo->get_num_bloque() );		
	
	//me fijo si cayo en algun hijo, en caso de ser asi, les setteo
	//los izq y derecho. 
	//Tener en cuenta que el elemento ahora conserva como datos los
	//del que se ubicaba en el medio pero izq y derecho del que produjo
	//overflow.
	if( result == -1 ){
		nodo_izquierdo.set_ref_izq(elem->izq);
		nodo_izquierdo.set_ref_der(elem->der);	
	}
	else{
		if( result == 1 ){
			nodo_derecho.set_ref_izq(elem->izq);
			nodo_derecho.set_ref_der(elem->der);
		}
		else{
			nodo_izquierdo.set_ref_der(elem->izq);
			nodo_derecho.set_ref_izq(elem->der);
		}
	}
	//guardo todos los bloques
	Buffer::get_instance()->guardar_bloque(*this, raiz->get_bloque() );
	Buffer::get_instance()->guardar_bloque(*this, derecho);
	Buffer::get_instance()->guardar_bloque(*this, izquierdo);
	
	//libero los bloques creados
	delete derecho;
	delete izquierdo;
	
}

bool ArbolB::manejar_overflow(Nodo * padre, Nodo * hijo, ElemNodo * elem){

	Debug::get_instance()->mostrar_mensaje("<ARBOL> Se produjo un overflow en un nodo del arbol " + this->get_nombre() + ".");
	
	//obtengo el bloque nuevo y lo guardo en el nodo
	Nodo * nodo_nuevo = new Nodo(get_bloque_libre(0), elem->clave, elem->dato);
	
	//divido el nodo que me llega en dos, con el dato que desborda.
	//Ahora me devolvio el que estaba el medio, que es el que va al padre
	char result = hijo->dividir_nodo(nodo_nuevo, &elem->clave, (TipoDato**)(&elem->dato));
	
	//si no es una hoja, es decir overflow encadenado.
	if( hijo->get_nivel() != 0 ){
		//me fijo si cayo en algun hijo, en caso de ser asi, les setteo
		//los izq y derecho. 
		//Tener en cuenta que el elemento ahora conserva como datos los
		//del que se ubicaba en el medio pero izq y derecho del que produjo
		//overflow.
		if( result == -1 ){
			hijo->set_ref_izq(elem->izq);
			hijo->set_ref_der(elem->der);	
		}
		else{
			if( result == 1 ){
				nodo_nuevo->set_ref_izq(elem->izq);
				nodo_nuevo->set_ref_der(elem->der);
			}
			else{
				hijo->set_ref_der(elem->izq);
				nodo_nuevo->set_ref_izq(elem->der);
			}
		}
	}
	
	//asigno los nuevos valores para izq y derecho
	elem->izq = hijo->get_bloque()->get_num_bloque();
	elem->der = nodo_nuevo->get_bloque()->get_num_bloque();
			
	//guardo los hijos porque ya estan listos
	Buffer::get_instance()->guardar_bloque(*this, nodo_nuevo->get_bloque());
	Buffer::get_instance()->guardar_bloque(*this, hijo->get_bloque());
			
	//intento ingresar el del medio en el padre, si pudo, setteo el izq
	//y el derecho y listo. Si hubo error(es decir un nuevo overflow)
	//devuelvo en elem el padre avisando dicha situacion
	bool hay_lugar_padre = false;
		
	if( ! padre->ingresar_elemento(elem->clave, elem->dato) ){
		hay_lugar_padre = false;
		//le incremento en uno el nivel al padre
		//padre->set_nivel(padre->get_nivel() + 1);
		
	}
	else{
		//asgino el izq y el derecho del anterior en el bloque
		padre->set_ref_izq(elem->izq);
		padre->set_ref_der(elem->der);
		hay_lugar_padre = true;
		Buffer::get_instance()->guardar_bloque(*this, padre->get_bloque());
	}
	
	delete (nodo_nuevo->get_bloque());	
	delete nodo_nuevo;
	
	
	return hay_lugar_padre;
}

bool ArbolB::ingresar_interno(ElemNodo * elem, Nodo * nodo){
	//como siempre se inserta en las hojas, si no estoy en una, me vuelvo
	//a meter
	if( nodo->get_nivel() != 0 ){
		//descarto el resultado porque ya se que no esta, esto es para
		//posicionarme donde deberia
		//nodo->buscar_elemento(elem->clave);
		if( nodo->buscar_elemento(elem->clave) )
			return true;
		TipoDato * clave_actual = elem->clave->clonar();
		nodo->get_clave(clave_actual);
		//si la clave donde encontre es menor me meto por la izquierda,
		//caso contrario voy por la derecha
		Nodo * hijo = NULL;
		if( (*elem->clave) < (*clave_actual)  )
			hijo = new Nodo(Buffer::get_instance()->get_bloque(*this, nodo->get_ref_izq()), elem->clave,elem->dato);
		else
			hijo = new Nodo(Buffer::get_instance()->get_bloque(*this, nodo->get_ref_der()), elem->clave,elem->dato);
		
		delete clave_actual;
		//si no pudo ingresar, manejo el overflow
		if( !ingresar_interno(elem, hijo) ){
			if(manejar_overflow(nodo, hijo, elem) ){
				//si no se produjo un nuevo overflow, guardo el padre
				Buffer::get_instance()->guardar_bloque(*this, nodo->get_bloque());
			}
			else{
				//si se produjo nuevamente overflow, devuelvo false.
				//tener en cuenta que el elemento que rebalsa del padre
				//ya viene metido en elem, es decir, esta actualizado.
				delete (hijo->get_bloque());
				delete hijo;
				return false;
			}
				
		}
		delete (hijo->get_bloque());
		delete hijo; //borro el hijo porque no se usa mas
			
		return true;
	}
	else{
		//lo ingreso, si no entraba aviso que hubo overflow, en caso contrario
		//guardo el bloque tocado
		if( ! nodo->ingresar_elemento(elem->clave, elem->dato) )	
			return false;
		else{
			Buffer::get_instance()->guardar_bloque(*this, nodo->get_bloque() );
			return true;
		}
	}
		
		
}

		
bool ArbolB::quitar(TipoDato* clave) throw(ExcepArchCerrado, ExcepErrorTipos, ExcepLeerBloque){
	bool quito = false;
	
	if( fd != -1){
		assert(base != NULL);//ESTO ROMPE SI NO HICIERON LAS COSAS BIEN
		
		if( clave->get_codigo_tipo() != base->get_codigo_tipo() )
			throw ExcepErrorTipos("Error - La clave es de tipo incorrecto");
			
			Debug::get_instance()->mostrar_mensaje("<ARBOL> Se quita un elemento en el arbol " + this->get_nombre() + "." );
			//TipoInt * dato_consultado = consultar(clave);
			//if (dato_consultado != NULL ){
			//Verifico que el registro tenga menor tamanio que el bloque

			//obtengo la raiz
			Bloque * raiz = Buffer::get_instance()->get_bloque(*this,_NODO_RAIZ_);
			//creo un nodo nuevo, le paso estos valores porque ya estan
			//verificados los tipos
			TipoInt * dato = new TipoInt();
			Nodo * nodo_raiz = new Nodo(raiz, clave, dato);
			delete dato;
			//llamo al quitar recursivo, si devuelve false quiere decir
			//que no lo pudo quitar, caso contrario devuelve true
			quito = quitar_interno(nodo_raiz ,clave);
				
			delete nodo_raiz;
			delete raiz;
			

		//}
		//else{
			//delete dato_consultado;
			//return false;		
		//}
	}
	else
		throw ExcepArchCerrado("Error - El archivo : "+ this-> get_nombre() +" esta cerrado. ");
	return quito;
}

void ArbolB::intercambiar_con_menor_mayores(Nodo * nodo, TipoDato * clave){
	
	//me posiciono donde esta el elem a cambiar. Como es interno, se que
	//va a estar si o si
	nodo->buscar_elemento(clave);
	unsigned short int ref_der_nodo = nodo->get_ref_der();
	unsigned short int ref_izq_nodo = nodo->get_ref_izq();
	TipoInt * dato = new TipoInt();
	//primero leo el derecho que es donde estan los mayores y luego
	//siempre la izquierda
	Nodo * nodo_intercambio = new Nodo(Buffer::get_instance()->get_bloque(*this,nodo->get_ref_der()),clave, dato);
	Nodo * aux;
	//busco el menor de los mayores (se encuentra en el nivel 0)
	while( nodo_intercambio->get_nivel() != 0 ){
		aux = nodo_intercambio;
		nodo_intercambio = new Nodo(Buffer::get_instance()->get_bloque(*this,aux->get_ref_izq()),clave, dato);
		delete (aux->get_bloque());
		delete aux;
		aux = NULL;
	}
	//me posiciono en el menor de todos, el primero
	nodo_intercambio->primero();
	//creo un tipo dato para la clave con la cual intercambio y el dato
	TipoDato * clave_intercambio = clave->clonar();
	TipoInt  * dato_intercambio = new TipoInt();
	nodo_intercambio->get_clave(clave_intercambio);
	nodo_intercambio->get_dato(dato_intercambio);
	
	//le asigno al dato base el dato que tenia el que voy a reemplazar.
	//La clave ya la tengo porque viene por param
	nodo->get_dato(dato);
	
	//hago el intercambio
	nodo->quitar_elemento(clave);
	nodo_intercambio->quitar_elemento(clave_intercambio);
	nodo->ingresar_elemento(clave_intercambio, dato_intercambio);
	//le asigno las referencias que pierdo al quitar
	nodo->set_ref_der(ref_der_nodo);
	nodo->set_ref_izq(ref_izq_nodo);
	//aca ingreso pero no setteo derecha ya que es hoja y no importa
	nodo_intercambio->ingresar_elemento(clave, dato);
	
	//guardo ambos bloques
	Buffer::get_instance()->guardar_bloque(*this, nodo->get_bloque());
	Buffer::get_instance()->guardar_bloque(*this, nodo_intercambio->get_bloque());
	
	//libero todo lo que cree
	delete (nodo_intercambio->get_bloque());
	delete nodo_intercambio;
	delete clave_intercambio;
	delete dato_intercambio;
	delete dato;
	
}
bool ArbolB::hay_underflow(Nodo * hijo){
	
	unsigned int ocupado = hijo->get_bloque()->get_tope() ;
	ocupado -= 4; //LE RESTO EL TAG TRUCHO
	unsigned int tam_bloque = hijo->get_bloque()->get_size() - 8;
	unsigned int tam_dato = 0;
	
	if( hijo->get_nivel() == 0 )
		tam_dato = 8;
	else
		tam_dato = 10;
	
	ocupado /= tam_dato;
	tam_bloque /= tam_dato;
	
	if( ocupado < (unsigned int)( _PORCENTAJE_MIN_ * tam_bloque ) )
		 return true;
	return false;
	
}

bool ArbolB::prestar_elemento(Nodo * padre, Nodo * hijo, Nodo * vecino, bool vecino_derecho ){
	TipoDato * clave_del_vecino = padre->get_clave_base();
	TipoInt  * dato_del_vecino  = new TipoInt(0);
	if( vecino_derecho)
		//Si el que me presta es el derecho, me voy al primero del vecino
		vecino->primero();
	else
		//si me presta el izquierdo, voy al ultimo
		vecino->ultimo();
	//quito el elemento prestado
	vecino->get_clave(clave_del_vecino);
	vecino->get_dato(dato_del_vecino);
	//Guardo las referencias del vecino ya que en caso de reinstertar
	//o meterlo, las necesito
	unsigned int ref_der_vecino = vecino->get_ref_der();
	unsigned int ref_izq_vecino = vecino->get_ref_izq();
	unsigned int ref_izq_hijo   = hijo->get_ref_izq();
	vecino->quitar_elemento();
	//si me queda en underflow el vecino, lo vuelvo a meter
	if( hay_underflow(vecino) ){
		vecino->ingresar_elemento(clave_del_vecino, dato_del_vecino);
		vecino->set_ref_der(ref_der_vecino);
		vecino->set_ref_izq(ref_izq_vecino);
		delete clave_del_vecino;
		delete dato_del_vecino;	
		return false;
	}
	else{
		//si no hay underflow, quiere decir que le podia prestar, entonces
		//saco el elem donde estoy parado en el padre y se lo agrego al hijo
		TipoDato * clave_del_padre = padre->get_clave_base();
		TipoInt  * dato_del_padre  = new TipoInt(0);
		padre->get_clave(clave_del_padre);
		padre->get_dato(dato_del_padre);
		padre->quitar_elemento();
		hijo->ingresar_elemento(clave_del_padre, dato_del_padre);
		//libero la memoria
		delete clave_del_padre;
		delete dato_del_padre;
		//le ingreso al padre el del vecino
		padre->ingresar_elemento(clave_del_vecino, dato_del_vecino);
		//como quite, restauro los punteros
		if(vecino_derecho){
			padre->set_ref_der(vecino->get_bloque()->get_num_bloque());
			padre->set_ref_izq(hijo->get_bloque()->get_num_bloque());
			hijo->set_ref_der(ref_izq_vecino);
			vecino->set_ref_izq(ref_der_vecino);
		}
		else{
			padre->set_ref_der(hijo->get_bloque()->get_num_bloque());
			padre->set_ref_izq(vecino->get_bloque()->get_num_bloque());
			hijo->set_ref_izq(ref_der_vecino);
			hijo->set_ref_der(ref_izq_hijo);
			vecino->set_ref_der(ref_izq_vecino);
		}
		//guardo los bloques modificados
		Buffer::get_instance()->guardar_bloque(*this,padre->get_bloque());
		Buffer::get_instance()->guardar_bloque(*this,vecino->get_bloque());
		Buffer::get_instance()->guardar_bloque(*this,hijo->get_bloque());
		
	}
	delete clave_del_vecino;
	delete dato_del_vecino;
	
	return true;
	
	
}

bool ArbolB::redistribuir( Nodo * nodo, Nodo * hijo, bool hijo_derecho ){
	Nodo * vecino = NULL;
	TipoDato * clave_del_vecino = nodo->get_clave_base();
	TipoInt  * dato_del_vecino  = new TipoInt(0);
	bool presto = false;
	
	//discrimino si era el hijo izquierdo o derecho porque me viene posicionado
	//entonces si primero le pido prestado al hijo izquierdo (por convencion), 
	//tengo que tener en cuenta que si no es derecho debo moverme 1 lugar 
	//para la izquierda para obtener el izquierdo del izquierdo
	if( !hijo_derecho){
		bool tenia_anterior = nodo->anterior();
		if( tenia_anterior ){
			//significa que me pude mover, es decir, no estaba en el borde	
			vecino = new Nodo(Buffer::get_instance()->get_bloque(*this, nodo->get_ref_izq()), clave_del_vecino ,dato_del_vecino);
			presto = prestar_elemento(nodo, hijo, vecino, false);
		}	
		if( tenia_anterior && (!presto) ){
			nodo->siguiente();
			delete (vecino->get_bloque());
			delete vecino;
		}
		if( !presto ){
			vecino = new Nodo(Buffer::get_instance()->get_bloque(*this, nodo->get_ref_der()), clave_del_vecino ,dato_del_vecino);
			presto = prestar_elemento(nodo, hijo, vecino, true);
		}
			
	}
	else{
		//si era el hijo derecho, no me tengo que desplazar para el izq
		vecino = new Nodo(Buffer::get_instance()->get_bloque(*this, nodo->get_ref_izq()), clave_del_vecino ,dato_del_vecino);
		presto = prestar_elemento(nodo, hijo, vecino, false);
		if( !presto ){
			//si no presto, avanzo al proximo
			if( nodo->siguiente() ){
				//si pudo avanzar, leo el proximo vecino
				delete (vecino->get_bloque());
				delete vecino;
				vecino = new Nodo(Buffer::get_instance()->get_bloque(*this, nodo->get_ref_der()), clave_del_vecino ,dato_del_vecino);	
				presto = prestar_elemento(nodo, hijo, vecino, true);
				if( !presto )
					nodo->anterior();//devuelvo posicionado donde me llego
			}
		}
		
	}
	delete clave_del_vecino;
	delete dato_del_vecino;
	delete (vecino->get_bloque());
	delete vecino;
	return presto;	
}

void ArbolB::concatenar(Nodo * padre, Nodo * hijo, bool hijo_derecho){
	//concateno siempre con el izquierdo salvo que sea el izquierdo del
	//primer nodo
	
	unsigned short int ref = 0;
	bool uno_con_izquierdo = false;
	if(!hijo_derecho){
		if( !padre->anterior() ){
			//si era el hijo izquierdo pero no el borde, es decir, tiene anterior
			//padre->siguiente();
			ref = padre->get_ref_der();
		}
		else{
			//vuelvo a donde estaba
			//padre->siguiente();
			//si era derecho o no era el de la punta, tomo el de la izquierda
			ref = padre->get_ref_izq();
			uno_con_izquierdo = true;
		}
	}
	else{
		uno_con_izquierdo = true;
		ref = padre->get_ref_izq();
	}
	
	bool actualizar_izquierdo = false;
	if(padre->siguiente()){
		actualizar_izquierdo = true;
		padre->anterior();
	}
	
	TipoDato * clave_padre = this->base->clonar();
	TipoInt  * dato_padre  = new TipoInt(0);
	//leo el elemento desde el padre
	padre->get_clave(clave_padre);
	padre->get_dato(dato_padre);
	//quito ese elemento del padre
	padre->quitar_elemento();
	//obtengo el hijo con el que concateno
	Nodo * hijo_concat = new Nodo(Buffer::get_instance()->get_bloque(*this, ref), clave_padre, dato_padre);
	
	if( uno_con_izquierdo ){
		Nodo * aux = hijo;
		hijo = hijo_concat;
		hijo_concat = aux;
	}
	//ingreso en el hijo el elemento del padre
	hijo->ultimo();
	//guardo esta ref porque la pierdo cuando ingreso
	unsigned short int ref_der = hijo->get_ref_der();
	hijo->ingresar_elemento(clave_padre, dato_padre);
	//obtengo la ref del derecho para no perderlo
	hijo_concat->primero();
	hijo->set_ref_der(hijo_concat->get_ref_izq());
	hijo->set_ref_izq(ref_der);
	//uno los nodos
	hijo->unir(hijo_concat);
		 		
	delete clave_padre;
	clave_padre = NULL;
	delete dato_padre;
	dato_padre = NULL;
	
	//si el padre no quedo vacio
	if( !padre->vacio() ){
		//si concatene en el derecho, setteo la ref derecha y si lo hice en
		//lado izquierdo, setteo el nuevo izq
		/*if(hijo_derecho){
			padre->anterior();
			padre->set_ref_der(hijo->get_bloque()->get_num_bloque() );
		}
		else
			padre->set_ref_izq(hijo->get_bloque()->get_num_bloque() );
		*/
		if( actualizar_izquierdo )
			padre->set_ref_izq(hijo->get_bloque()->get_num_bloque() );
		
		
	}
	else{
		//si el padre quedo vacio, le ingreso los elems del hijo
		//que contiene lo concatenado.  Ya queda con el nivel corresp
		char* contenido = new char[hijo->get_bloque()->get_tope()];
		hijo->get_bloque()->leer(contenido, 0, hijo->get_bloque()->get_tope());
		padre->get_bloque()->escribir(contenido, 0, hijo->get_bloque()->get_tope());
		delete[] (contenido);
		//vacio el hijo
		hijo->vaciar();
		//lo agrego como disponible
		bloques_libres->append( hijo->get_bloque()->get_num_bloque() );
		
	}
	//vacio el hijo concatenado, lo guardo y lo asigno como libre
	//hijo_concat->get_bloque()->vaciar();
	Buffer::get_instance()->guardar_bloque(*this, hijo_concat->get_bloque());
	bloques_libres->append( hijo_concat->get_bloque()->get_num_bloque() );
	//guardo el hijo
	Buffer::get_instance()->guardar_bloque(*this, hijo->get_bloque());
	//guardo el padre
	Buffer::get_instance()->guardar_bloque(*this, padre->get_bloque());
		
	if( uno_con_izquierdo ){
		Nodo * aux = hijo;
		hijo = hijo_concat;
		hijo_concat = aux;
	}
	delete (hijo_concat->get_bloque());
	delete hijo_concat;
	
	
	

	
}
void ArbolB::manejar_underflow( Nodo * nodo, Nodo * hijo, bool hijo_derecho ){
	
	if( !redistribuir( nodo, hijo, hijo_derecho ) ){
		Debug::get_instance()->mostrar_mensaje("<ARBOL> Se produjo underflow en un nodo del arbol " + this->get_nombre() + ". Se concatenan nodos." );	
		concatenar(nodo, hijo, hijo_derecho);
	}
	else
		Debug::get_instance()->mostrar_mensaje("<ARBOL> Se produjo underflow en un nodo del arbol " + this->get_nombre() + ". Se pudo redistribuir." );	
	
		
}

bool ArbolB::quitar_interno(Nodo * nodo, TipoDato * clave, void ** param){
	
	if( nodo->get_nivel() != 0 ){
		
		Nodo * hijo = NULL;
		bool hijo_derecho = false;
		if( nodo->buscar_elemento(clave) ){
			//si lo encontro, como no estoy en una hoja, lo cambio por
			//el menor de los mayores	
			intercambiar_con_menor_mayores(nodo, clave);
			//la primera vez me muevo al reves porque el elem es menor
			//que el actual, pero quedo a la derecha en el intercambio
			TipoInt * dato_base = new TipoInt(); //asi ocupa 4 B =P
			hijo = new Nodo(Buffer::get_instance()->get_bloque(*this, nodo->get_ref_der()), clave,dato_base);
			hijo_derecho = true;
			delete dato_base;
		}
		else{
			//si la clave donde encontre es menor me meto por la izquierda,
			//caso contrario voy por la derecha.
			TipoDato * clave_actual = clave->clonar();
			nodo->get_clave(clave_actual);
			TipoInt * dato_base = new TipoInt(); //asi ocupa 4 B =P
			if( (*clave) < (*clave_actual) )
				hijo = new Nodo(Buffer::get_instance()->get_bloque(*this, nodo->get_ref_izq()), clave,dato_base);
			else{
				hijo_derecho = true;
				hijo = new Nodo(Buffer::get_instance()->get_bloque(*this, nodo->get_ref_der()), clave,dato_base);
			}
			delete clave_actual;
			delete dato_base;
		}
		 		
		bool quito = quitar_interno(hijo, clave, param);
		//si quito y quedo en undeflow el nodo, lo manejo
		if( quito && hay_underflow(hijo) )
			manejar_underflow( nodo, hijo, hijo_derecho );
		delete (hijo->get_bloque());
		delete hijo;
		return quito;
	}
	else{
		bool quito = nodo->quitar_elemento(clave);
		if(quito)
			Buffer::get_instance()->guardar_bloque(*this, nodo->get_bloque());
		//en el caso de una hoja solo intento quitar y devuelvo si fue exitoso
		return quito;
	}	
}
		
TipoInt * ArbolB::consultar(TipoDato* clave) throw(ExcepArchCerrado,ExcepLeerBloque){
	
	Debug::get_instance()->mostrar_mensaje("<ARBOL> Se consulta en el arbol " + this->get_nombre() + ".");
	TipoInt * retorno = NULL;
	if (this-> fd != -1){
		//obtengo la raiz
		Bloque * raiz = Buffer::get_instance()->get_bloque(*this,_NODO_RAIZ_);
		//creo un nodo nuevo, le paso estos valores porque ya estan
		//verificados los tipos
		TipoInt base_dato(0);
		Nodo * nodo_raiz = new Nodo(raiz,clave, &base_dato);
		consultar_interno(nodo_raiz,clave, &retorno);
		
		delete raiz;
		delete nodo_raiz;
	}
	else
		throw ExcepArchCerrado("Error - El archivo : "+ this-> get_nombre() +" esta cerrado. ");	
	
	return retorno;
}

void ArbolB::consultar_interno(Nodo * nodo, TipoDato * clave, TipoInt ** retorno ){
	//condicion de corte: nivel 0
	if( nodo->get_nivel() == 0 ){
		if( nodo->buscar_elemento(clave) ){
			//si la encuentro la devuelvo
			(*retorno) = new TipoInt(0);
			nodo->get_dato(*retorno);
		}
		else
			/**
			 * Aca habias puesto (retorno = NULL) y te lo cambie por
			 *  (*retorno = NULL)
			 */
			*retorno = NULL;
	}
	else{
		//condicion de corte: encontrado en la hoja
		if( nodo->buscar_elemento(clave) ){
			(*retorno) = new TipoInt(0);
			nodo->get_dato(*retorno);
		}
		else{
			TipoDato* clave_actual = base->clonar();
			nodo->get_clave(clave_actual);
			//si la clave donde encontre es menor me meto por la izquierda,
			//caso contrario voy por la derecha
			Nodo * hijo = NULL;
			if ( (*clave) < (*clave_actual) ) {
				TipoInt dato;
				hijo = new Nodo(Buffer::get_instance()->get_bloque(*this, nodo->get_ref_izq()), clave,&dato);
			}
			else{
				TipoInt dato;
				hijo = new Nodo(Buffer::get_instance()->get_bloque(*this, nodo->get_ref_der()), clave,&dato);
			}
			consultar_interno(hijo, clave, retorno);
			delete (hijo->get_bloque());
			delete hijo;
			delete(clave_actual);
		}
	}
	
}


long ArbolB::get_tam() throw(ExcepArchCerrado){
	return this->cant_bloques * this->get_tam_bloque();
}
		
TiposArchivo ArbolB::get_tipo_archivo(){
	return NINGUNO;	
}

void ArbolB::escribir_cant_bloques(unsigned int cant){
	Bloque * bloque = Buffer::get_instance()->get_bloque(*this, 0);
	bloque->escribir((char*) &cant,0, TAM_REG);
	Buffer::get_instance()->guardar_bloque(*this, bloque);
	delete bloque;
}
		
unsigned int ArbolB::leer_cant_bloques(){
	unsigned int cant;
	Bloque * bloque = Buffer::get_instance()->get_bloque(*this, 0);
	bloque->leer((char*) &cant,0, TAM_REG);
	delete bloque;
	return cant;
}

void ArbolB::crear_bloque(unsigned short int nivel ) throw(ExcepEscribirBloque){
	
	Bloque * bloque = new Bloque(this->cant_bloques, this->get_tam_bloque());
	Nodo nodo(bloque, this->base);
	nodo.set_nivel(nivel);
	Buffer::get_instance()->guardar_bloque(*this, bloque);
	delete bloque;
	
	this->cant_bloques++;
}

Bloque * ArbolB::get_bloque_libre(unsigned short int nivel ){
	//pido un bloque nuevo para lo que tengo que agregar
	unsigned int num_bloque_nuevo = bloques_libres->get_bloque_libre();
	if( num_bloque_nuevo == ArchBloquesLibres::ERROR ){
		//si no habia uno para usar, creo un bloque nuevo
		crear_bloque();
		num_bloque_nuevo = this->cant_bloques - 1;
	}
	Bloque * b = Buffer::get_instance()->get_bloque(*this, num_bloque_nuevo);
	Nodo nodo(b, this->base);
	nodo.set_nivel(nivel);
	return b;
	
}
unsigned int ArbolB::get_cant_regs() throw(ExcepArchCerrado){
	if( this->fd != -1){
		//obtengo la raiz
		Bloque * raiz = Buffer::get_instance()->get_bloque(*this,_NODO_RAIZ_);
		//creo un nodo nuevo, le paso estos valores porque ya estan
		//verificados los tipos
		TipoInt * dato_base = new TipoInt(0);
		Nodo * nodo_raiz = new Nodo(raiz,this->base, dato_base );
		
		unsigned int cant_regs = contar_regs(nodo_raiz);
		
		delete dato_base;
		delete raiz;
		delete nodo_raiz;
		return cant_regs;
	}
	else
		throw ExcepArchCerrado("Error - El archivo : "+ this-> get_nombre() +" esta cerrado. ");
	
	return 0;
}
unsigned int ArbolB::get_espacio_libre()  throw(ExcepArchCerrado, ExcepLeerBloque){
	if( this->fd != -1){
		//aca sumo los que estan totalmente libres
		unsigned int espacio_libre = bloques_libres->get_cantidad_elementos();
		espacio_libre *=  this->get_tam_bloque();
		//le agrego los del bloque del header
		//espacio_libre += (this->get_tam_bloque()) - 4;		
		//le agrego el espacio libre dentro de los nodos
		//obtengo la raiz
		Bloque * raiz = Buffer::get_instance()->get_bloque(*this,_NODO_RAIZ_);
		//creo un nodo nuevo, le paso estos valores porque ya estan
		//verificados los tipos
		TipoInt * dato_base = new TipoInt(0);
		Nodo * nodo_raiz = new Nodo(raiz,this->base, dato_base );
		espacio_libre += espacio_libre_nodos(nodo_raiz);
		
		delete dato_base;
		delete raiz;
		delete nodo_raiz;
				
		return espacio_libre;
	}
	else
		throw ExcepArchCerrado("Error - El archivo : "+ this-> get_nombre() +" esta cerrado. ");
	
	return 0;
}
unsigned int ArbolB::contar_regs(Nodo * nodo){
	
	unsigned int cant_regs = 0;
	if( nodo->get_nivel() != 0 ){
		bool ok = true;
		Nodo * hijo = NULL;
		do{	
			cant_regs++;
			hijo = new Nodo(Buffer::get_instance()->get_bloque(*this, nodo->get_ref_izq()), this->base,this->base_hoja);
			cant_regs += contar_regs(hijo);
			delete (hijo->get_bloque());
			delete hijo;
			hijo = NULL;
			ok = nodo->siguiente();
		}while(ok);
		hijo = new Nodo(Buffer::get_instance()->get_bloque(*this, nodo->get_ref_der()), this->base,this->base_hoja);
		cant_regs += contar_regs(hijo);
		delete (hijo->get_bloque());
		delete hijo;
		hijo = NULL;
		
		return cant_regs;
	}
	else{
		if(!nodo->vacio()){
			bool ok = false;
			do{
				cant_regs++;
				ok = nodo->siguiente();
			}while( ok );
		}
		return cant_regs;
	}
}
unsigned int ArbolB::espacio_libre_nodos(Nodo * nodo){
	
	unsigned int espacio_libre = 0;
	if( nodo->get_nivel() != 0 ){
		bool ok = false;
		Nodo * hijo = NULL;
		espacio_libre += nodo->get_bloque()->get_espacio_libre();
		do{				
			hijo = new Nodo(Buffer::get_instance()->get_bloque(*this, nodo->get_ref_izq()), this->base,this->base_hoja);
			espacio_libre += espacio_libre_nodos(hijo);
			delete (hijo->get_bloque());
			delete hijo;
			hijo = NULL;
			ok = nodo->siguiente();
		}while(ok);
		hijo = new Nodo(Buffer::get_instance()->get_bloque(*this, nodo->get_ref_der()), this->base,this->base_hoja);
		espacio_libre += espacio_libre_nodos(hijo);
		delete (hijo->get_bloque());
		delete hijo;
		hijo = NULL;
		
		return espacio_libre;
	}
	else{
		espacio_libre += nodo->get_bloque()->get_espacio_libre();
		return espacio_libre;
	}
}



void ArbolB::set_tipo_base(TipoDato &base){
	if (this->base != NULL)
		delete this->base;
	this->base = base.clonar();
}
